package LearnDataStructure.d_图结构.f_最短路径by单元.网络流最短路径;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 17:04
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.f_最短路径by单元.网络流最短路径
 */
public class g_Floyd {

    public static void main(String[] args) {
        g_Floyd test = new g_Floyd();
        test.useFloyd();
    }

    public void useFloyd() {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        final int N = 65535;
        //这是一个无向图
        int[][] matrix = new int[][]{
               //a  b  c  d  e  f  g
                {0, 5, 7, N, N, N, 2},//a
                {5, 0, N, 9, N, N, 3},//b
                {7, N, 0, N, 8, N, N},//c
                {N, 9, N, 0, N, 4, N},//d
                {N, N, 8, N, 0, 5, 4},//e
                {N, N, N, 4, 5, 0, 6},//f
                {2, 3, N, N, 4, 6, 0} //g
        };
        Graph graph = new Graph(vertex.length, matrix, vertex);
        System.out.println("算法执行前...");
        graph.showGraph();
        System.out.println("算法执行后...");
        graph.Floyd();
        graph.showGraph();
        System.out.println("展示A->D的最短路径...");
        graph.showShortestPath(0,3);
    }



    public class Graph {
        //存放顶点的数组
        public char[] vertex;
        //保存从各个顶点出发到其它顶点的距离；最后算法返回的结果，也是保留在该数组
        public int[][] dis;
        //保存到达目标项点的前驱项点;动态生成
        public int[][] pre;
        final int N = 65535;

        /**
         * @param lengthOfVertex 顶点数组的大小
         * @param matrix         邻接矩阵
         * @param vertex         顶点数组
         */
        public Graph(int lengthOfVertex, int[][] matrix, char[] vertex) {
            this.vertex = vertex;
            this.dis = matrix;
            this.pre = new int[lengthOfVertex][lengthOfVertex];

            //对pre[][]初始化；存放的是前驱顶点的下标
            for (int i = 0; i < lengthOfVertex; i++) {
                for (int j = 0; j < lengthOfVertex; j++) {
                    pre[i][j] = N;
                }
            }
            /*
            尚硅谷的填充手法
             a   b   c   d
            a0   0   0   0
            b1   1   1   1
            c2   2   2   2
            d3   3   3   3
            我没用，我直接填充的N == 65535
             */
        }

        /**
         * 展示pre[][],dis[][]
         */
        public void showGraph() {
            System.out.println("展示pre[][]");
            for (int i = 0; i < dis.length; i++) {
                if (i == 0) {
                    for (int j = 0; j < dis.length; j++) {
                        System.out.print(vertex[j] + "\t");
                    }
                    System.out.println();
                }

                for (int j = 0; j < dis.length; j++) {
                    if (pre[i][j] == N) {
                        System.out.print("N" + "\t");
                    } else {
                        System.out.print(pre[i][j] + "\t");
                    }
                }
                System.out.print(vertex[i]);
                System.out.println();
            }

            System.out.println("展示dis[][]");
            for (int i = 0; i < dis.length; i++) {
                if (i == 0) {
                    for (int j = 0; j < dis.length; j++) {
                        System.out.print(vertex[j] + "\t");
                    }
                    System.out.println();
                }
                for (int j = 0; j < dis.length; j++) {
                    if (dis[i][j] == N) {
                        System.out.print("N" + "\t");
                    } else {
                        System.out.print(dis[i][j] + "\t");
                    }
                }
                System.out.print(vertex[i]);
                System.out.println();
            }
        }

        /**
         * O(N^3)
         */
        public void Floyd() {
            //用来保存每一次路径长度的比较结果
            int tempLength = 0;
            //v代表中间节点；每个顶点都尝试充当一次中间节点
            for (int v = 0; v < dis.length; v++) {
                //start代表开始节点；start -> end就这两个节点的路径长度   与   start -> v -> end三个节点的路径长度作比较
                for (int start = 0; start < dis.length; start++) {
                    for (int end = 0; end < dis.length; end++) {
                        //求从start -> v -> end的路径长度；可能会得到无穷大(没有边)
                        tempLength = dis[start][v] + dis[v][end];
                        //判断dis[start][end] > dis[start][v] + dis[v][end]
                        if (dis[start][end] > tempLength) {
                            //更新start -> end的最短路径
                            dis[start][end] = tempLength;
                            //更新start -> end的中间节点
                            // pre[start][end] = pre[v][end];
                            pre[start][end] = v;
                        }
                    }
                }
            }
        }

        /**
         * 递归实现
         * @param start
         * @param end
         */
        public void showShortestPath(int start, int end) {
            if (pre[start][end] == N) {
                System.out.println((char)('A' + start) + " -> " + (char)('A' + end));
                return;
            }
            int v = pre[start][end];
            showShortestPath(start,v);
            showShortestPath(v,end);
        }
    }
}
